import java.util.Arrays;

public class Sort {

    public void insertSort(int[] arr,int left,int right){
        for(int i=1;i<arr.length;i++){
            for (int j = i-1; j >=0 ; j--) {
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
    }

    public void xuanZe(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min=i;
              for (int j = i+1; j < arr.length; j++) {
            if(arr[min]>arr[j]){
                  min=j;
            }

            }
          int tmp=arr[i];
              arr[i]=arr[min];
              arr[min]=tmp;

        }
    }

    public void xiEr(int[] arr){
          int gap =arr.length/2;
          while(gap>0){
          xiErSort(arr,gap);
          gap/=2;
          }
    }

    public void xiErSort(int[] arr,int gap){  //希尔排序

        for (int i = gap; i <arr.length ; i++) {
            for (int j = i-gap; j >=0; j-=gap) {
                if(arr[j+gap]<arr[j]){
                    int tmp=arr[j+gap];
                    arr[j+gap]=arr[j];
                    arr[j]=tmp;
                }
            }
        }
    }
    public void qSort(int[] arr,int left,int right){
        if(left>=right){
            return;
        }
        int prior = getPrior(arr,left,right);
        qSort(arr,left,prior-1);
        qSort(arr,prior+1,right);
    }

    public int getPrior(int[] arr,int left,int right){
        int prior = arr[left];
        while(left<right){
            while(left<right&&arr[right]>=prior){
                right--;
            }
            arr[left] = arr[right];
            while(left<right&&arr[left]<=prior){
                left++;
            }
            arr[right]=arr[left];
        }
        arr[left]=prior;
        return left;
    }

    public static void main1(String[] args) {
        int[] arr = new int[]{9,8,7,6,5,4,3,2,1};
        Sort sort = new Sort();
     sort.xiEr(arr);
        System.out.println(Arrays.toString(arr));
    }/*
    public static int[] merge (int[] arr,int left,int right){

        if(left==right){
            return new int[]{arr[left]};
        }
        int mid  = (left+right)/2;
        int[] leftArr =  merge(arr,left,mid);
        int[] rightArr = merge(arr,mid+1,right);
  int[] tmp = new int[leftArr.length+rightArr.length];
        int i=0;
        int j=0;
        int k=0;
        while(i<leftArr.length&&j<rightArr.length){
            if(leftArr[i]<rightArr[j]){
                tmp[k]=leftArr[i];
                i++;
                k++;
            }else{
                tmp[k]=rightArr[j];
                j++;
                k++;
            }
        }
        if(i<leftArr.length){
            while(i<leftArr.length){
                tmp[k]=leftArr[i];
                k++;i++;
            }
        }
        if(j<rightArr.length){
            while(j<rightArr.length){
                tmp[k]=rightArr[j];
                k++;j++;
            }
        }
        return tmp;
    }

*/


    public static int[] merge (int[] arr,int left,int right){
        
        if(left==right){
            return new int[]{arr[left]};
        }
        int mid  = (left+right)/2;
      int[] leftArr =  merge(arr,left,mid);
       int[] rightArr = merge(arr,mid+1,right);
       arr = hebing(leftArr,rightArr);
       return arr;
    }

    private static int[] hebing(int[] leftArr,int[] rightArr) {
        int[] tmp = new int[leftArr.length+rightArr.length];

        int i=0;
        int j=0;
        int k=0;
        while(i<leftArr.length&&j<rightArr.length){
            if(leftArr[i]<rightArr[j]){
                tmp[k]=leftArr[i];
                i++;
                k++;
            }else{
                tmp[k]=rightArr[j];
                j++;
                k++;
            }
        }
        if(i<leftArr.length){
            while(i<leftArr.length){
                tmp[k]=leftArr[i];
                k++;i++;
            }
        }
        if(j<rightArr.length){
            while(j<rightArr.length){
                tmp[k]=rightArr[j];
                k++;j++;
            }
        }
        return tmp;
    }


    public static void main(String[] args){
        int[] arr = new int[]{9,8,7,6,5,4,3};
        arr=merge(arr,0,6);
        System.out.println(Arrays.toString(arr));
    }
}
